class Solution {
    /*
--------------------------------------------
拼的思维：1994
1000 900 90 4 结果是：MCMXCIV

打表思维

个位计算  十位计算 百位计算  千位计算
个位计算打表： I II III IV V VI VII VIII IX
十位计算打表： 10 20 30 40 50 60 70 80 90
              X XX XXX XL L LX LXX LXXX XC
百位计算打表： 100   200   300   400   500   600   700   800   900
              C     CC   CCC   CD     D    DC     DCC   DCCC  CM
千位计算打表：1000 2000 3000 （题设1 <= num <= 3999）
             M    MM    MMM
    */
    public String intToRoman(int num) {

        //将所有打表数据都塞入table
        Map<Integer, String> table = new HashMap<>();
        table.put(0,"");    //重要！如果是0，打表就是空
        table.put(1,"I");
        table.put(2,"II");
        table.put(3,"III");
        table.put(4,"IV");
        table.put(5,"V");
        table.put(6,"VI");
        table.put(7,"VII");
        table.put(8,"VIII");
        table.put(9,"IX");
        table.put(10,"X");
        table.put(20,"XX");
        table.put(30,"XXX");
        table.put(40,"XL");
        table.put(50,"L");
        table.put(60,"LX");
        table.put(70,"LXX");
        table.put(80,"LXXX");
        table.put(90,"XC");
        table.put(100,"C");
        table.put(200,"CC");
        table.put(300,"CCC");
        table.put(400,"CD");
        table.put(500,"D");
        table.put(600,"DC");
        table.put(700,"DCC");
        table.put(800,"DCCC");
        table.put(900,"CM");
        table.put(1000,"M");
        table.put(2000,"MM");
        table.put(3000,"MMM");

        int digit = 1;  //位数
        StringBuilder result = new StringBuilder();
        while (num != 0){
            //digit * (num % 10) 一定要加括号，注意运算顺序
            String roman = table.get(digit * (num % 10));//取最低位,并乘以位数,并查表，得到对应的罗马数字
            num = num/10;   //去掉最低位
            digit *= 10;    //位数乘数乘10
            result.insert(0,roman);
        }

        return result.toString();
    }

    //解法2：贪心策略
    public String intToRoman(int num) {
        int[] values={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        String[] rom={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

        StringBuilder sb=new StringBuilder();

        for(int i=0;i<values.length;i++){
            while(num>=values[i]){
                sb.append(rom[i]);
                num-=values[i];
            }
        }

        return sb.toString();
    }

}
